package com.scott.ch210.greedy;

import java.util.ArrayList;
import java.util.List;

/**
 * @author 黄后林
 * @version 1.0
 * @note
 * @date 2022-06-12 20:42:04
 */
public class CoinChange {


    public int coinChange(int[] c ,int k){

        // 1、回溯穷举所有的硬币组合
        List<Integer>      coins = new ArrayList<>();
        List<List<Integer>> rs   = new ArrayList<>();

        dfs(k,c,coins,rs);

        // 2、如果没有任何硬币组合相加等于k则返回-1
        if(rs.isEmpty()){

            return -1;
        }

        // 3、找到硬币数最少的硬币组合 [ 找到路径最短的 ]
        int min =0;
        for( int i =1; i<rs.size();i++){
            if(rs.get(i).size() < rs.get(min).size()){
                min=i;
            }
        }
        return rs.get(min).size();
    }

    /**
     * 方法描述:
     * @author: 黄后林
     * @date: 2022/6/12 20:48
     * @param k
     * @param c     初始化的硬币的数组
     * @param coins 选中的硬币的数组
     * @param rs
     */
    private void dfs(int k, int[] c, List<Integer> coins,List<List<Integer>> rs){

        if(k < 0){
            return;
        }

        if(k == 0){
            rs.add(new ArrayList<>(coins));
            return;
        }

        for(int i =0 ;i< c.length;i++){

            coins.add(c[i]);

            dfs(k-c[i],c,coins,rs);

            // 删除最后1个 ?
            coins.remove(coins.size() -1 );

        }
    }

    public static void main(String[] args) {
        CoinChange cc = new CoinChange();
        int[] c = {3,5};
        int k = 11;
        int rs = cc.coinChange(c, k);
        System.out.println(rs);
    }
}
